import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

// 有重复项数组的去重全排列
// 测试链接 : https://leetcode.cn/problems/permutations-ii/
public class PermutationWithoutRepetition {
    public List<List<Integer>> permuteUnique(int[] nums) {

        List<List<Integer>> ans = new ArrayList<>();
        func(nums,0,ans);

        return ans;
    }

    public void func(int[] nums, int pos, List<List<Integer>> ans ){
        if(pos == nums.length){
            List<Integer> temp = new ArrayList<>();
            for(int num : nums){
                temp.add(num);
            }
            ans.add(temp);
        }else{
            HashSet<Integer> set = new HashSet<>();
            for(int j = pos; j < nums.length; j++){

                if(!set.contains(nums[j])) {
                    set.add(nums[j]);
                    swap(nums,j,pos);
                    func(nums,pos+1,ans);
                    swap(nums,j,pos);
                }
            }
        }
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
